Growth rate (group theory)

In group theory, the growth rate of a group with respect to a symmetric generating set describes the size of balls in the group. Every element in the group can be written as a product of generators, and the growth rate counts the number of elements that can be written as a product of length n.

Contents

Definition

Suppose G is a finitely generated group; and T is a finite symmetric set of generators (symmetric means that if  x \in T then  x^{-1} \in T ). Any element  x \in G can be expressed as a word in the T-alphabet

 x = a_1 \cdot a_2 \cdots a_k \mbox{ where } a_i\in T.

Let us consider the subset of all elements of G which can be presented by such a word of length ≤ n

B_n(G,T) = \{x\in G | x = a_1 \cdot a_2 \cdots a_k \mbox{ where } a_i\in T \mbox{ and } k\le n\}.

This set is just the closed ball of radius n in the word metric d on G with respect to the generating set T:

B_n(G,T) = \{x\in G | d(x, e)\le n\}.

More geometrically, B_n(G,T) is the set of vertices in the Cayley graph with respect to T which are within distance n of the identity.

Given two nondecreasing positive functions a and b one can say that they are equivalent (a\sim b) if there is a constant C such that

 a(n/ C) \leq b(n) \leq a(Cn),\,

for example  p^n\sim q^n if  p,q>1 .

Then the growth rate of the group G can be defined as the corresponding equivalence class of the function

\#(n)=|B_n(G,T)|,

where |B_n(G,T)| denotes the number of elements in the set B_n(G,T). Although the function \#(n) depends on the set of generators T its rate of growth does not (see below) and therefore the rate of growth gives an invariant of a group.

The word metric d and therefore sets B_n(G,T) depend on the generating set T. However, any two such metrics are bilipschitz equivalent in the following sense: for finite symmetric generating sets E, F, there is a positive constant C such that

 {1\over C} \ d_F(x,y) \leq d_{E}(x,y) \leq C \ d_F(x,y).

As an immediate corollary of this inequality we get that the growth rate does not depend on the choice of generating set.

Polynomial and exponential growth

If

\#(n)\le C(n^k%2B1)

for some C,k<\infty we say that G has a polynomial growth rate. The infimum k_0 of such k's is called the order of polynomial growth. According to Gromov's theorem, a group of polynomial growth is virtually nilpotent, i.e. it has a nilpotent subgroup of finite index. In particular, the order of polynomial growth k_0 has to be a natural number and in fact \#(n)\sim n^{k_0}.

If \#(n)\ge a^n for some a>1 we say that G has an exponential growth rate. Every finitely generated G has at most exponential growth, i.e. for some b>1 we have \#(n)\le b^n.

If \#(n) grows more slowly than any exponential function, G has a subexponential growth rate. Any such group is amenable.

Examples

See also

References

Further reading